1. Field of the Invention
This application relates to apparatus and a method for determining relationships among physical spatial entities. More specifically, this invention relates to a technique for compensating for definitional variations in terms employed to describe spatial relationships among physical spatial entities.
2. Description of Related Art
For many applications such as land use planning and environmental studies, it is necessary to define and determine physical relationships between physical spatial entities such as adjacent land areas. For example, in the context of environmental studies, it may be necessary to determine the number of industrial facilities located adjacent to a particular river. Although at first blush this may seem like a trivial task, a number of problems exist.
Definitions are one source of problems. The terms employed to describe the physical relationships are extremely context sensitive. The term "adjacent" when describing the land areas in which particular animal populations are found is quite different than what is meant when that term is employed to describe the relationship of an industrial site and a river, since animals roam and their boundaries are inherently imprecise. Both uses of the term are quite different than when the term is employed to describe the positioning of transistors in an integrated circuit, since the scale is so much smaller. Even within the same context, definitions can vary. The term "intersection" means something different in the lexicon of British topographers as compared to American topographers.
A second problem exists regarding the collection of information necessary to assess the physical relationships between physical spatial entities. Of course, it is always possible to send out a team to travel to the location of the spatial entities to determine the appropriate relationships. This obviously becomes quite expensive and time consuming, particularly when the spatial entities cover extensive portions of the globe.
In this age of the computer, spatial data bases or geographic information systems have been developed for storing information related to two or three dimensional physical spatial entities. Such systems store vector or raster descriptions of spatial entities including altitudes, alpha-numeric descriptors and the like. They are designed to store and process data for which spatial location is an important component of the information content of the data. The critical concern for the development of a geographic information system is the integration of a wide variety of diverse information with location as the criteria for the relationships.
A problem with such spatial data bases is that there is a great amount of information contained within the data. If land parcels are described in coordinates, it is difficult to tell if the parcels are next to each other. Furthermore, it is usually unclear exactly what is meant by the phrase next to. Suppose one parcel of land is described by corner posts and another parcel is described by lines. It is difficult to compare the physical relationship of these two parcels.
Furthermore, even with geographic information systems, definitions of relational terms is very context sensitive.
In order to determine relationships between physical spatial entities, Intergraph Corporation, of Huntsville, Ala., developed its Spatial Analyst.TM. system. This system breaks down spatial information in a data base into its most basic elements consisting of faces, edges and nodes. Nodes are distinguished points. Edges are nonintersecting curves between nodes. Faces are connected areas not on edges or nodes. Thus, for example, in FIG. 3, the numbered circles represent nodes, the numbered lines represent edges and the numbered areas represent faces. Once information in the data base is defined in terms of these three basic types of elements, certain relationships between two elements can then be determined. According to the Spatial Analyst.TM. system, twenty-seven specific categories define the possible relationships between a face and either another face, an edge or a node, an edge and either another edge or a node, and two nodes. The particular elements to be analyzed are then compared one at a time with the twenty-seven different possibilities to establish which of those possibilities describes the relationship between the two elements being analyzed.
With this approach, large numbers of computer program steps are necessary to conduct the one-at-a-time type searching among the twenty-seven different possibilities for each intuitive relationship an operator might wish to establish. Intuitive relationships, as the term is used in this patent, are those relationships and comparisons made upon spatial data which are characterized by human intuition. In the prior art, such intuitive relationships are typically characterized by large ad hoc computer programs that examine spatial data elements in a manner that is difficult or impossible to define precisely other than to examine the steps of the computer program itself. Of course, a large number of intuitive relationships might be desired. Furthermore, the spatial comparison of elements in the data base with each of the twenty-seven possible situations is a very complex process that takes a great deal of computing time.
Pullar and Egenhofer in "Toward Formal Definitions of Topological Relations Among Spatial Objects", presented at the Third International Symposium on Spatial Data Handling at Sydney, Australia, August, 17-19, 1988, published by the Surveying Engineering Program, University of Maine, attempts to establish basic definitions of topological relations among spatial objects. This paper sets forth a proposition that six relationships are all that are necessary to define topological relations. This paper merely seeks to define topological relationships without suggesting any techniques for assessing the relationships among spatial objects.